{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest Subsequence of Distinct Characters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #string #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #字符串 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestSubsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不同字符的最小子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>返回 <code>s</code> 字典序最小的子序列，该子序列包含 <code>s</code> 的所有不同字符，且只包含一次。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong><code>s = \"bcabc\"</code>\n",
    "<strong>输出<code>：</code></strong><code>\"abc\"</code>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong><code>s = \"cbacdcbc\"</code>\n",
    "<strong>输出：</strong><code>\"acdb\"</code></pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>s</code> 由小写英文字母组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong>该题与 316 <a href=\"https://leetcode.cn/problems/remove-duplicate-letters/\">https://leetcode.cn/problems/remove-duplicate-letters/</a> 相同</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-subsequence-of-distinct-characters](https://leetcode.cn/problems/smallest-subsequence-of-distinct-characters/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-subsequence-of-distinct-characters](https://leetcode.cn/problems/smallest-subsequence-of-distinct-characters/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"bcabc\"', '\"cbacdcbc\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        st = []\n",
    "        n = len(s)\n",
    "        cnt = s.count(letter)\n",
    "        t = n - k\n",
    "        p = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            x = s[i]\n",
    "            while st and st[-1] > x and t > 0:\n",
    "                if st[-1] == letter:\n",
    "                    if repetition > p - 1 + cnt:\n",
    "                        break\n",
    "                    p -= 1\n",
    "\n",
    "                st.pop()\n",
    "                t -= 1\n",
    "\n",
    "            st.append(x)\n",
    "\n",
    "            if x == letter:\n",
    "                p += 1\n",
    "                cnt -= 1\n",
    "\n",
    "        while len(st) > k:\n",
    "            if st[-1] == letter:\n",
    "                p -= 1\n",
    "\n",
    "            st.pop()\n",
    "\n",
    "        for i in range(k - 1, -1, -1):\n",
    "            if p < repetition and st[i] != letter:\n",
    "                st[i] = letter\n",
    "                p += 1\n",
    "\n",
    "        return ''.join(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, a: str, k: int, l: str, r: int) -> str:\n",
    "        n = len(a)\n",
    "        m = len([j for j in a if j==l]) #至少r次\n",
    "        b = n-k\n",
    "        s = []\n",
    "        for j in a:\n",
    "            while s and (j<s[-1]) and b:\n",
    "                if s[-1]!=l:\n",
    "                    s.pop() \n",
    "                    b -= 1 \n",
    "                else:\n",
    "                    if m>r:\n",
    "                        s.pop()\n",
    "                        b-=1 \n",
    "                        m-=1 \n",
    "                    else:\n",
    "                        break \n",
    "            s.append(j) \n",
    "        c = []\n",
    "        while b:\n",
    "            t = s.pop()\n",
    "            if t!=l:\n",
    "                b-=1 \n",
    "            else:\n",
    "                if m>r:\n",
    "                    b-=1 \n",
    "                    m-=1 \n",
    "                else:\n",
    "                    c.append(t)\n",
    "        s += c \n",
    "        return ''.join(s)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        n = len(s)\n",
    "\n",
    "        cnt = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] == letter: cnt += 1\n",
    "\n",
    "        \n",
    "        toErase = n - k\n",
    "\n",
    "        res = []\n",
    "        p = 0\n",
    "\n",
    "        for i in range(n):\n",
    "\n",
    "            while (toErase and res and s[i] < res[-1]):\n",
    "                if res[-1] == letter:\n",
    "\n",
    "                    if repetition > p - 1 + cnt:\n",
    "                        break\n",
    "                    p -= 1\n",
    "                res.pop()\n",
    "                toErase -= 1\n",
    "            \n",
    "            if s[i] == letter:\n",
    "                p += 1\n",
    "                cnt -= 1\n",
    "            res.append(s[i])\n",
    "        \n",
    "        while len(res) > k:\n",
    "            if res[-1] == letter:\n",
    "                p -= 1\n",
    "            res.pop()\n",
    "        \n",
    "        for i in range(k - 1, -1, -1):\n",
    "            if p < repetition and res[i] != letter:\n",
    "                res[i] = letter\n",
    "                p += 1\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        cnt = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] == letter: cnt += 1\n",
    "\n",
    "        \n",
    "        toErase = n - k\n",
    "\n",
    "        res = []\n",
    "        p = 0\n",
    "\n",
    "        for i in range(n):\n",
    "\n",
    "            while (toErase and res and s[i] < res[-1]):\n",
    "                if res[-1] == letter:\n",
    "\n",
    "                    if repetition > p - 1 + cnt:\n",
    "                        break\n",
    "                    p -= 1\n",
    "                res.pop()\n",
    "                toErase -= 1\n",
    "            \n",
    "            if s[i] == letter:\n",
    "                p += 1\n",
    "                cnt -= 1\n",
    "            res.append(s[i])\n",
    "        \n",
    "        while len(res) > k:\n",
    "            if res[-1] == letter:\n",
    "                p -= 1\n",
    "            res.pop()\n",
    "        \n",
    "        for i in range(k - 1, -1, -1):\n",
    "            if p < repetition and res[i] != letter:\n",
    "                res[i] = letter\n",
    "                p += 1\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        # 单调栈去维护字典序最小的定长子序列，注意限制条件。\n",
    "        n = len(s)\n",
    "        cnt = Counter(s)\n",
    "        sta = []\n",
    "        inside_num = 0\n",
    "        for i,c in enumerate(s):\n",
    "            remain = n - i\n",
    "            if c == letter:\n",
    "                cnt[letter] -= 1\n",
    "            while sta and sta[-1]>c:\n",
    "                if len(sta) + remain == k:\n",
    "                    break\n",
    "                if sta[-1]!=letter:\n",
    "                    sta.pop(-1)\n",
    "                else:\n",
    "                    if inside_num + cnt[letter] > repetition:\n",
    "                        inside_num -= 1\n",
    "                        sta.pop(-1)\n",
    "                    else:\n",
    "                        break\n",
    "            if c == letter:\n",
    "                if len(sta)<k:\n",
    "                    sta.append(c)\n",
    "                    inside_num+=1\n",
    "                else:\n",
    "                    if inside_num + cnt[letter] + 1 == repetition:\n",
    "                        idx = len(sta) - 1\n",
    "                        while idx>=0 and sta[idx]==letter:\n",
    "                            idx -= 1\n",
    "                        sta[idx] = letter\n",
    "                        inside_num+=1\n",
    "            else: \n",
    "                if len(sta)<k:\n",
    "                    sta.append(c)\n",
    "        return \"\".join(sta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        n = len(s)\n",
    "        re = s.count(letter)\n",
    "        pre = 0\n",
    "        st = []\n",
    "        for i, ch in enumerate(s):\n",
    "            while st and st[-1] > ch and len(st) + n - i > k:\n",
    "                if st[-1] == letter:\n",
    "                    if pre - 1 + re < repetition:\n",
    "                        break\n",
    "                    pre -= 1\n",
    "                st.pop()\n",
    "            if ch == letter:\n",
    "                pre += 1\n",
    "                re -= 1\n",
    "            st.append(ch)\n",
    "\n",
    "        while len(st) > k:\n",
    "            if st[-1] == letter:\n",
    "                pre -= 1\n",
    "            st.pop()\n",
    "        \n",
    "        for i in range(k - 1, -1, -1):\n",
    "            if pre < repetition:\n",
    "                if st[i] != letter:\n",
    "                    st[i] = letter\n",
    "                    pre += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return ''.join(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        # 求出经典的s中k长度的最小字典序子序列\n",
    "        n = len(s)\n",
    "        cnt = Counter(s)\n",
    "        sta = []\n",
    "        inside_num = 0\n",
    "        for i,c in enumerate(s):\n",
    "            remain = n - i  #剩下的字符数（包括当前的s[i]）\n",
    "            if c == letter:\n",
    "                cnt[letter] -= 1\n",
    "            while sta and sta[-1]>c:\n",
    "                if len(sta) + remain == k:\n",
    "                    break\n",
    "                if sta[-1]!=letter:\n",
    "                    sta.pop(-1)\n",
    "                else:\n",
    "                    if inside_num + cnt[letter] > repetition:\n",
    "                        inside_num -= 1\n",
    "                        sta.pop(-1)\n",
    "                    else:\n",
    "                        break\n",
    "            if c == letter:\n",
    "                if len(sta)<k:\n",
    "                    sta.append(c)\n",
    "                    inside_num+=1\n",
    "                else:\n",
    "                    if inside_num + cnt[letter] + 1 == repetition:\n",
    "                        idx = len(sta) - 1\n",
    "                        while idx>=0 and sta[idx]==letter:\n",
    "                            idx -= 1\n",
    "                        sta[idx] = letter\n",
    "                        inside_num+=1\n",
    "            else: \n",
    "                if len(sta)<k:\n",
    "                    sta.append(c)\n",
    "        return \"\".join(sta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        m,n = s.count(letter)-repetition,len(s)-k\n",
    "        v = 0\n",
    "        st = []\n",
    "        for c in s:\n",
    "            while st and st[-1]>c and n:\n",
    "                if st[-1]==letter:\n",
    "                    if m==0: break\n",
    "                    m -= 1\n",
    "                n -= 1\n",
    "                st.pop()\n",
    "            st.append(c)\n",
    "        st = st[:k]\n",
    "        cnt = st[:k].count(letter)\n",
    "        if cnt < repetition:\n",
    "            t = repetition-cnt\n",
    "            for i in range(k-1,-1,-1):\n",
    "                if st[i] != letter:\n",
    "                    st[i] = letter\n",
    "                    t -= 1\n",
    "                    if t == 0: break\n",
    "        return ''.join(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "\n",
    "        left = s.count(letter)\n",
    "        stack = []\n",
    "        t = len(s) - k\n",
    "        for ch in s:\n",
    "\n",
    "            while t and stack and ch < stack[-1]:\n",
    "                if stack[-1] == letter:\n",
    "                    if left - 1 < repetition:\n",
    "                        break\n",
    "                    stack.pop()\n",
    "                    left -= 1\n",
    "                    t -= 1\n",
    "                else:\n",
    "                    stack.pop()\n",
    "                    t -= 1\n",
    "            \n",
    "            stack.append(ch)\n",
    "        # print(stack)\n",
    "        stack = stack[:k]\n",
    "        c = stack.count(letter)\n",
    "        if c < repetition:\n",
    "            for j in range(k - 1, -1, -1):\n",
    "                if stack[j] != letter:\n",
    "                    stack[j] = letter\n",
    "                    c += 1\n",
    "                    if c >= repetition:\n",
    "                        break\n",
    "        return ''.join(stack)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        n = len(s)\n",
    "        nCounter = Counter(s)\n",
    "        remaing = n\n",
    "        \n",
    "        stack = []\n",
    "        for s_i in s:\n",
    "            while stack and remaing > k and stack[-1] > s_i and \\\n",
    "                (  (stack[-1]!=letter) or (nCounter[stack[-1]] > repetition)):\n",
    "                nCounter[stack.pop()] -= 1\n",
    "                remaing -= 1\n",
    "            stack.append(s_i)\n",
    "        print(stack)\n",
    "        \n",
    "        # 如果 前k个里面 letter 数目不够，就从后向前删除 非 letter的，删一个在最后补一个letter\n",
    "        stack_k = stack[:k]\n",
    "        cur_n_letter = Counter(stack_k)[letter]\n",
    "        i = k-1\n",
    "        while cur_n_letter < repetition:\n",
    "            while stack_k[i] == letter:\n",
    "                i -= 1\n",
    "            stack_k.pop(i)\n",
    "            i -= 1\n",
    "            stack_k.append(letter)\n",
    "            cur_n_letter += 1\n",
    "        print(stack_k)\n",
    "\n",
    "        return(''.join(stack_k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        n = len(s)\n",
    "        ls = [i for i, ch in enumerate(s) if ch == letter]\n",
    "        q = deque()\n",
    "        res = []\n",
    "        for i, ch in enumerate(s):\n",
    "            while q and s[q[-1]] > ch:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "            \n",
    "            while n - i == k or (repetition > 0 and i == ls[-repetition]):\n",
    "                j = q.popleft()\n",
    "                if k > 0 and (k > repetition or s[j] == letter):\n",
    "                    res.append(s[j])\n",
    "                    k -= 1\n",
    "                    repetition -= (res[-1] == letter)\n",
    "\n",
    "        return ''.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        ct = 0\n",
    "        pres = [0]\n",
    "        for l in s:\n",
    "            if l == letter:\n",
    "                pres.append(pres[-1] + 1)\n",
    "            else:\n",
    "                pres.append(pres[-1])\n",
    "        st = []\n",
    "        n = len(s)\n",
    "        for i,l in enumerate(s):\n",
    "\n",
    "            while st and l < st[-1] and ct - [0,1][st[-1] == letter] + pres[-1] - pres[i] >= repetition and len(st) - 1 + n - i >= k:\n",
    "                ct -= [0,1][st.pop() == letter]\n",
    "            st.append(l)\n",
    "            ct += [0,1][l == letter]\n",
    "        \n",
    "        q = deque()\n",
    "        while len(st) + len(q) > k:\n",
    "            top = st[-1]\n",
    "            if top == letter:\n",
    "                st.pop()\n",
    "                if ct > repetition:\n",
    "                    ct -= 1\n",
    "                else:\n",
    "                    q.appendleft(top)\n",
    "            else:\n",
    "                st.pop()\n",
    "        st.extend(list(q))\n",
    "        return \"\".join(st)\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        n = len(s)\n",
    "        ls = [i for i, ch in enumerate(s) if ch == letter]\n",
    "        q = deque()\n",
    "        res = []\n",
    "        for i, ch in enumerate(s):\n",
    "            while q and s[q[-1]] > ch:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "            \n",
    "            while n-i == k or (repetition > 0 and i == ls[-repetition]):\n",
    "                j = q.popleft()\n",
    "                if k > 0 and (k > repetition or s[j] == letter):\n",
    "                    # print(i,s[j])\n",
    "                    res.append(s[j])\n",
    "                    k -= 1\n",
    "                    repetition -= (res[-1] == letter)\n",
    "\n",
    "        return ''.join(res)\n",
    "\n",
    "            \n",
    "                \n",
    "            \n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from typing import List, Tuple  \n",
    "from collections import deque, Counter  \n",
    "from queue import PriorityQueue  \n",
    "import math  \n",
    "from functools import lru_cache  \n",
    "from sortedcontainers import SortedDict  \n",
    "import random  \n",
    "import copy  \n",
    "import sys  \n",
    "sys.setrecursionlimit(999999999)  \n",
    "  \n",
    "# 单调栈获取长度为k的最小子序列(不要求连续), 要求至少包含rep 个 letter\n",
    "def min_sequence_with_letter(s: List, k, letter, rep):  \n",
    "    n = len(s)  \n",
    "    if k > n:  \n",
    "        return None  \n",
    "    if k == n:  \n",
    "        return list(s)  \n",
    "  \n",
    "    A = [0] * n  \n",
    "    A[-1] = 0 if s[-1] != letter else 1  \n",
    "    for i in range(n-2, -1, -1):  \n",
    "        A[i] = A[i+1]  \n",
    "        if s[i] == letter:  \n",
    "            A[i] += 1  \n",
    "  \n",
    "    letter_cnt = 0      # stack中已经有的letter计数  \n",
    "  \n",
    "    stack = [0] * k  \n",
    "    s_idx = 0  \n",
    "    for idx, v in enumerate(s):  \n",
    "        # 将栈中偏大的数值淘汰掉, 淘汰的前提是淘汰完之后字符总数还能凑够K个，且letter个数还能凑够rep个  \n",
    "        while True:  \n",
    "            if s_idx > 0:  \n",
    "                cnt = letter_cnt if stack[s_idx-1] != letter else letter_cnt - 1  \n",
    "            else:  \n",
    "                cnt = 0  \n",
    "  \n",
    "            if s_idx > 0 and v < stack[s_idx-1] and (n - idx - 1) + s_idx >= k and cnt + A[idx] >= rep:  \n",
    "                pop_v = stack[s_idx-1]  \n",
    "                s_idx -= 1  \n",
    "                if pop_v == letter:  \n",
    "                    letter_cnt -= 1  \n",
    "            else:  \n",
    "                break  \n",
    "  \n",
    "        # 将栈里面多占了letter的位置的非letter数值淘汰掉  \n",
    "        if v == letter:  \n",
    "            while stack[s_idx-1] != letter and k - s_idx + letter_cnt < rep:  \n",
    "                s_idx -= 1  \n",
    "  \n",
    "        if s_idx < k:  \n",
    "            stack[s_idx] = v  \n",
    "            s_idx += 1  \n",
    "  \n",
    "            if v == letter:  \n",
    "                letter_cnt += 1  \n",
    "  \n",
    "    return stack  \n",
    "  \n",
    "class Solution:  \n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:  \n",
    "        return ''.join(min_sequence_with_letter(s, k, letter, repetition))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from typing import List, Tuple\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(999999999)\n",
    "\n",
    "\n",
    "# 单调栈获取长度为k的最小子序列(不要求连续), 要求至少包含rep 个 letter\n",
    "def min_sequence_with_letter(s: List, k, letter, rep):\n",
    "    n = len(s)\n",
    "    if k > n:\n",
    "        return None\n",
    "    if k == n:\n",
    "        return list(s)\n",
    "\n",
    "    A = [0] * n\n",
    "    A[-1] = 0 if s[-1] != letter else 1\n",
    "    for i in range(n - 2, -1, -1):\n",
    "        A[i] = A[i + 1]\n",
    "        if s[i] == letter:\n",
    "            A[i] += 1\n",
    "\n",
    "    letter_cnt = 0  # stack中已经有的letter计数\n",
    "\n",
    "    stack = [0] * k\n",
    "    s_idx = 0\n",
    "    for idx, v in enumerate(s):\n",
    "        # 将栈中偏大的数值淘汰掉, 淘汰的前提是淘汰完之后字符总数还能凑够K个，且letter个数还能凑够rep个\n",
    "        while True:\n",
    "            if s_idx > 0:\n",
    "                cnt = letter_cnt if stack[s_idx - 1] != letter else letter_cnt - 1\n",
    "            else:\n",
    "                cnt = 0\n",
    "\n",
    "            if s_idx > 0 and v < stack[s_idx - 1] and (n - idx - 1) + s_idx >= k and cnt + A[idx] >= rep:\n",
    "                pop_v = stack[s_idx - 1]\n",
    "                s_idx -= 1\n",
    "                if pop_v == letter:\n",
    "                    letter_cnt -= 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        # # 将栈里面多占了letter的位置的非letter数值淘汰掉\n",
    "        # if v == letter:\n",
    "        #     while stack[s_idx - 1] != letter and k - s_idx + letter_cnt < rep:\n",
    "        #         s_idx -= 1\n",
    "\n",
    "        t = 1 if v == letter else 0\n",
    "\n",
    "        if s_idx < k and (letter_cnt + t + (k-s_idx-1) >= rep):\n",
    "            stack[s_idx] = v\n",
    "            s_idx += 1\n",
    "\n",
    "            if v == letter:\n",
    "                letter_cnt += 1\n",
    "\n",
    "    return stack\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        return ''.join(min_sequence_with_letter(s, k, letter, repetition))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\r\n",
    "        n = len(s)\r\n",
    "\r\n",
    "        #----后缀，右侧出现指定字母的次数\r\n",
    "        suffix_cnt = [0 for _ in range(n)]\r\n",
    "        acc = 0\r\n",
    "        for i in range(n - 1, -1, -1):\r\n",
    "            acc += (s[i] == letter)\r\n",
    "            suffix_cnt[i] = acc\r\n",
    "        \r\n",
    "        stk = []\r\n",
    "        x = 0           #letter在res中已经出现的次数\r\n",
    "        for i in range(0, n):\r\n",
    "            y = x       #因为可能会操作，操作过程中letter在res中出现的次数\r\n",
    "            #----弹栈\r\n",
    "            while stk != [] and len(stk) + (n - i - 1) >= k and s[i] < stk[-1]:\r\n",
    "                if stk[-1] == letter:\r\n",
    "                    y -= 1\r\n",
    "                if y + suffix_cnt[i] < repetition:\r\n",
    "                    break\r\n",
    "                #--正式删\r\n",
    "                stk.pop(-1)\r\n",
    "                x = y\r\n",
    "\r\n",
    "            #----压栈\r\n",
    "            if len(stk) < k:\r\n",
    "                if s[i] == letter or k - len(stk) > repetition - x:\r\n",
    "                    stk.append(s[i])\r\n",
    "                    if s[i] == letter:\r\n",
    "                        x += 1\r\n",
    "        \r\n",
    "        return ''.join(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        n = len(s)\n",
    "        suffix_cnt = [0 for _ in range(n)]\n",
    "        acc = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            acc += (s[i] == letter)\n",
    "            suffix_cnt[i] = acc\n",
    "        stk = []\n",
    "        x = 0\n",
    "        for i in range(0, n):\n",
    "            y = x\n",
    "            while stk != [] and len(stk) + (n - i - 1) >= k and s[i] < stk[-1]:\n",
    "                if stk[-1] == letter:\n",
    "                    y -= 1\n",
    "                if y + suffix_cnt[i] < repetition:\n",
    "                    break\n",
    "                stk.pop(-1)\n",
    "                x = y\n",
    "            if len(stk) < k:\n",
    "                if s[i] == letter or k - len(stk) > repetition - x:\n",
    "                    stk.append(s[i])\n",
    "                    if s[i] == letter:\n",
    "                        x += 1\n",
    "        return ''.join(stk)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 通过时间：12m38s，单调栈\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        stack = []\n",
    "        numdict = {}\n",
    "        instack = {}\n",
    "        for stri in s:\n",
    "            if numdict.get(stri) == None:\n",
    "                numdict[stri] = 0\n",
    "            numdict[stri] += 1\n",
    "        for stri in s:\n",
    "            if instack.get(stri) != None:\n",
    "                numdict[stri] -= 1\n",
    "                continue\n",
    "            while stack and stack[-1] > stri and numdict.get(stack[-1]) > 0:\n",
    "                instack.pop(stack[-1])\n",
    "                stack.pop()\n",
    "            stack.append(stri)\n",
    "            instack[stri] = 1\n",
    "            numdict[stri] -= 1\n",
    "            # print(stack, stri, numdict[stri])\n",
    "        return ''.join(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        if len(s)==0 or len(s)==1:\n",
    "            return s\n",
    "        stack=[s[0]]\n",
    "        l=len(set(s))\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i] in stack:\n",
    "                continue\n",
    "            if s[i]<stack[-1]:\n",
    "                while stack and  stack[-1]>s[i] and stack[-1] in s[i+1:]:\n",
    "                    stack.pop()\n",
    "                stack.append(s[i])\n",
    " \n",
    "            if s[i]>stack[-1] and s[i] not in stack:\n",
    "                stack.append(s[i])\n",
    "\n",
    "        return \"\".join(stack)\n",
    "                    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            if s[i] not in stack:\n",
    "                while stack and s[i] < stack[-1] and stack[-1] in s[i+1:]:\n",
    "                    stack.pop()\n",
    "                stack.append(s[i])\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "        n = len(c.keys())\n",
    "        stack = []\n",
    "        for i in s:\n",
    "            if i in stack:\n",
    "                c[i] -= 1\n",
    "                continue\n",
    "            while stack and stack[-1] > i:\n",
    "                if c[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    break\n",
    "            stack.append(i)\n",
    "            c[i] -= 1\n",
    "        return \"\".join(stack)[:n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        stk = []\n",
    "        count = defaultdict(int)\n",
    "        for char in s:\n",
    "            count[char]+=1\n",
    "\n",
    "        for char in s:\n",
    "            count[char]-=1\n",
    "            if char in stk:\n",
    "                continue\n",
    "            else:\n",
    "                while(len(stk)!=0 and stk[-1]>char):\n",
    "                    if count[stk[-1]]==0:\n",
    "                        break\n",
    "                    else:\n",
    "                        stk.pop()\n",
    "                stk.append(char)\n",
    "                print(stk)\n",
    "\n",
    "        return \"\".join(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        # 存放去重的结果\n",
    "        stk = []\n",
    "        # 布尔数组初始值为 false，记录栈中是否存在某个字符\n",
    "        # 输入字符均为 ASCII 字符，所以大小 256 够用了\n",
    "        inStack = [False] * 256\n",
    "        count = [0] * 256\n",
    "\n",
    "        for c in s:\n",
    "            count[ord(c)] += 1\n",
    "\n",
    "        for c in s:\n",
    "            count[ord(c)] -= 1\n",
    "            # 如果字符 c 存在栈中，直接跳过\n",
    "            if inStack[ord(c)]:\n",
    "                continue\n",
    "            while stk and stk[-1] > c and count[ord(stk[-1])] > 0:\n",
    "                inStack[ord(stk.pop())] = False\n",
    "            # 若不存在，则插入栈顶并标记为存在\n",
    "            stk.append(c)\n",
    "            inStack[ord(c)] = True\n",
    "\n",
    "        # 栈中元素插入顺序是反的，需要 reverse 一下\n",
    "        return ''.join(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        stack = [] \n",
    "        counter  = collections.Counter(s)\n",
    "        for c in s:\n",
    "            if c not in stack:\n",
    "                while stack and c < stack[-1] and counter[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "\n",
    "                stack.append(c)\n",
    "            counter[c]-=1\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        counts = {}\n",
    "        for ss in s:\n",
    "            counts[ss] = counts.get(ss, 0) + 1\n",
    "        \n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c not in stack:\n",
    "                while stack and ord(stack[-1]) > ord(c) and counts[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "                \n",
    "                stack.append(c)\n",
    "            \n",
    "            counts[c] -= 1\n",
    "        \n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        stack = []\n",
    "        count = Counter(s)\n",
    "        for c in s:\n",
    "            count[c] -= 1\n",
    "            if c not  in stack:\n",
    "                while stack and stack[-1] > c and count[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "                stack.append(c)\n",
    "        return \"\".join(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        d = Counter(s)\n",
    "        stack = []\n",
    "        for i in s:\n",
    "            d[i] -= 1\n",
    "            if i in stack:\n",
    "                continue\n",
    "            while stack and stack[-1] > i and d[stack[-1]] > 0:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return ''.join(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            char = s[i]\n",
    "            if char in res:\n",
    "                continue\n",
    "            while len(res) != 0 and res[-1] > char and s.find(res[-1], i) != -1:\n",
    "                res.pop()\n",
    "            res.append(char)\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        left = Counter(s)\n",
    "        in_ans = set()\n",
    "        ans = []\n",
    "        for c in s:\n",
    "            left[c] -= 1\n",
    "            if c in in_ans:\n",
    "                continue\n",
    "            while ans and c < ans[-1] and left[ans[-1]]:\n",
    "                in_ans.remove(ans.pop())\n",
    "            ans.append(c)\n",
    "            in_ans.add(c)\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        left = collections.Counter(s)\n",
    "        ans = []\n",
    "        ans_in = set()\n",
    "        for c in s:\n",
    "            left[c] -= 1\n",
    "            if c in ans_in:\n",
    "                continue\n",
    "            while ans and c<ans[-1] and left[ans[-1]]:\n",
    "                ans_in.remove(ans.pop())\n",
    "            ans.append(c)\n",
    "            ans_in.add(c)\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "\n",
    "        st = []\n",
    "        sts = set()\n",
    "\n",
    "        for i, x in enumerate(s):\n",
    "            if not st:\n",
    "                st.append(i)\n",
    "                sts.add(x)\n",
    "            else:\n",
    "                if x not in sts:\n",
    "                    while st and s[st[-1]] >= x and s[st[-1]] in s[i:]:\n",
    "                        j = st.pop()\n",
    "                        sts.remove(s[j])\n",
    "\n",
    "                    st.append(i)\n",
    "                    sts.add(x)\n",
    "\n",
    "        return ''.join(s[i] for i in st)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "import sys\n",
    "import random\n",
    "# sys.setrecursionlimit(100000)\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        st = []\n",
    "        cnt = Counter(s)\n",
    "        vis = set()\n",
    "        for c in s:\n",
    "            if c in vis:\n",
    "                cnt[c] -= 1\n",
    "                continue\n",
    "            while st and c <= st[-1]:\n",
    "                if cnt[st[-1]] > 0:\n",
    "                    vis.remove(st[-1])\n",
    "                    st.pop()\n",
    "                else:\n",
    "                    break\n",
    "            vis.add(c)\n",
    "            st.append(c)\n",
    "            cnt[c] -= 1\n",
    "\n",
    "                \n",
    "        return ''.join(st)\n",
    "s = Solution()\n",
    "s.smallestSubsequence('cdadabcc')\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        seen = set()\n",
    "        cnt = Counter(s)\n",
    "        st = []\n",
    "        for ch in s:\n",
    "            if ch not in seen:\n",
    "                while st and ch < st[-1] and cnt[st[-1]] > 0:\n",
    "                    seen.discard(st.pop())\n",
    "                st.append(ch)\n",
    "                seen.add(ch)\n",
    "            cnt[ch] -= 1\n",
    "\n",
    "        return \"\".join(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        stk = []\n",
    "\n",
    "        # 维护一个计数器记录字符串中字符的数量\n",
    "        # 因为输入为 ASCII 字符，大小 256 够用了\n",
    "        count = [0] * 256\n",
    "        for i in range(len(s)):\n",
    "            count[ord(s[i])] += 1\n",
    "\n",
    "        in_stack = [False] * 256\n",
    "        for c in s:\n",
    "            # 每遍历过一个字符，都将对应的计数减一\n",
    "            count[ord(c)] -= 1\n",
    "\n",
    "            if in_stack[ord(c)]: continue\n",
    "\n",
    "            while stk and stk[-1] > c:\n",
    "                # 若之后不存在栈顶元素了，则停止 pop\n",
    "                if count[ord(stk[-1])] == 0:\n",
    "                    break\n",
    "                # 若之后还有，则可以 pop\n",
    "                in_stack[ord(stk.pop())] = False\n",
    "\n",
    "            stk.append(c)\n",
    "            in_stack[ord(c)] = True\n",
    "\n",
    "        return ''.join(stk)\n",
    "    # def smallestSubsequence(self, s: str) -> str:\n",
    "    #     count = defaultdict(int)\n",
    "    #     for c in s:\n",
    "    #         count[c] += 1\n",
    "    #     stack = []\n",
    "    #     inStack = defaultdict(bool)\n",
    "    #     for c in s:\n",
    "    #         if inStack[c]:  # 在考虑字符 s[i] 时，如果它已经存在于栈中，则不能加入字符 s[i]\n",
    "    #             continue\n",
    "    #         count[c] -= 1\n",
    "    #         # while stack and stack[-1] > c and count[c] > 0: # 【易错！】\n",
    "    #         while stack and stack[-1] > c and count[stack[-1]] > 0: \n",
    "    #             p = stack.pop()\n",
    "    #             inStack[p] = False\n",
    "    #         stack.append(c)\n",
    "    #         inStack[c] = True\n",
    "    #     return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        h=collections.Counter(s)\n",
    "        stack=[]\n",
    "\n",
    "        for char in s:\n",
    "            if char not in stack:\n",
    "                while stack and char<stack[-1] and h[stack[-1]]>0:\n",
    "                    stack.pop()\n",
    "                stack.append(char)\n",
    "            h[char]-=1\n",
    "        \n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        counter_dict = {}\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            counter_dict[s[i]] = counter_dict.get(s[i], 0) + 1\n",
    "        insubseq_set = set()\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            c = s[i]\n",
    "            counter_dict[c] -= 1\n",
    "            if c in insubseq_set:\n",
    "                continue\n",
    "            while ans and c < ans[-1] and counter_dict[ans[-1]] > 0:\n",
    "                insubseq_set.remove(ans.pop(-1))\n",
    "            ans.append(c)\n",
    "            insubseq_set.add(c)\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        fill = [False]*26\n",
    "        cnt = [0]*26\n",
    "        for c in s:\n",
    "            cnt[ord(c) - 97] += 1\n",
    "        ans = []\n",
    "        for c in s:\n",
    "            while ans and not fill[ord(c) - 97] and ord(c) < ord(ans[-1]) and cnt[ord(ans[-1]) - 97]:\n",
    "                fill[ord(ans.pop()) - 97] = False\n",
    "            if not fill[ord(c) - 97]:\n",
    "                ans.append(c)\n",
    "                fill[ord(c) - 97] = True\n",
    "            cnt[ord(c) - 97] -= 1\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return ''\n",
    "        \n",
    "        dic = {}    # 用来记录每个元素剩余出现次数\n",
    "        for x in s:\n",
    "            if x not in dic:\n",
    "                dic[x] = 1\n",
    "            else:\n",
    "                dic[x] += 1\n",
    "        \n",
    "        st = []  # 栈,当新加入的元素比栈顶元素小时，弹出栈顶元素\n",
    "        # 当栈顶元素在后续不再出现时，不弹出，当新加入的元素已经出现在栈中时，不再加入\n",
    "        for x in s:\n",
    "            if x not in st:\n",
    "                while len(st) > 0 and ord(x) < ord(st[-1]) and dic[st[-1]] >= 1:\n",
    "                    st.pop()\n",
    "                st.append(x)\n",
    "            dic[x] -= 1\n",
    "        return ''.join(st)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "\n",
    "        visited = {}\n",
    "        count = collections.Counter(s)\n",
    "        res_len = len(set(s))\n",
    "        stack = []\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            char = s[i]\n",
    "            while stack and stack[-1] > char and not char in visited and count[stack[-1]] > 0:\n",
    "                visited.pop(stack[-1])\n",
    "                stack.pop()\n",
    "            if not char in visited:\n",
    "                stack.append(char)\n",
    "                visited[stack[-1]] = 1\n",
    "            count[char] = count[char] - 1\n",
    "\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        # 从左往右扫，维持单调递减栈，并且统计词频，如果违反了 栈的单调性\n",
    "        # 并且后续子串中还有栈顶这个字符，就直接弹出，因为后续的那个字符会填充\n",
    "        # 进来，并且使其字典序更小\n",
    "        stack = []\n",
    "        cnt = Counter(s) # 统计字符的词频\n",
    "        for i, ch in enumerate(s):\n",
    "            cnt[ch] -= 1\n",
    "            if ch in stack:\n",
    "                continue\n",
    "            # 1、尝试着去淘汰栈顶元素\n",
    "            while stack and ch <= stack[-1] and cnt[stack[-1]] > 0:\n",
    "                stack.pop()\n",
    "\n",
    "            # 2、直接放入栈中\n",
    "            stack.append(ch)\n",
    "        return ''.join(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        count = defaultdict(int)\n",
    "        # count = dict()\n",
    "        for c in s:\n",
    "            count[c] += 1\n",
    "        stack = []\n",
    "        inStack = defaultdict(bool)\n",
    "        for c in s:\n",
    "            count[c] -= 1   # 注意这句话要在continue的前边\n",
    "            if inStack[c]:  # 在考虑字符 s[i] 时，如果它已经存在于栈中，则不能加入字符 s[i]\n",
    "                continue\n",
    "            \n",
    "            # while stack and stack[-1] > c and count[c] > 0: # 【易错！】\n",
    "            # while stack and stack[-1] > c and count[stack[-1]] > 0: \n",
    "            while stack and stack[-1] > c:\n",
    "                if count[stack[-1]] == 0:\n",
    "                    break\n",
    "                p = stack.pop()\n",
    "                inStack[p] = False\n",
    "            stack.append(c)\n",
    "            inStack[c] = True\n",
    "        return \"\".join(stack)\n",
    "\n",
    "\n",
    "    # def smallestSubsequence(self, s: str) -> str:\n",
    "    #     stk = []\n",
    "\n",
    "    #     # 维护一个计数器记录字符串中字符的数量\n",
    "    #     # 因为输入为 ASCII 字符，大小 256 够用了\n",
    "    #     count = [0] * 256\n",
    "    #     for i in range(len(s)):\n",
    "    #         count[ord(s[i])] += 1\n",
    "\n",
    "    #     in_stack = [False] * 256\n",
    "    #     for c in s:\n",
    "    #         # 每遍历过一个字符，都将对应的计数减一\n",
    "    #         count[ord(c)] -= 1\n",
    "\n",
    "    #         if in_stack[ord(c)]: continue\n",
    "\n",
    "    #         while stk and stk[-1] > c:\n",
    "    #             # 若之后不存在栈顶元素了，则停止 pop\n",
    "    #             if count[ord(stk[-1])] == 0:\n",
    "    #                 break\n",
    "    #             # 若之后还有，则可以 pop\n",
    "    #             in_stack[ord(stk.pop())] = False\n",
    "\n",
    "    #         stk.append(c)\n",
    "    #         in_stack[ord(c)] = True\n",
    "\n",
    "    #     return ''.join(stk)\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, text: str) -> str:\n",
    "        ans = [' ']\n",
    "        for i, c in enumerate(text):\n",
    "            if c not in ans:\n",
    "                while ans[-1] > c and ans[-1] in text[i: ]:\n",
    "                    ans.pop()\n",
    "                ans += [c]\n",
    "        return ''.join(ans[1: ])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        ans=['']\n",
    "        for i,x in enumerate(s):\n",
    "            if x not in ans:\n",
    "                while ans[-1]>x and ans[-1] in s[i:]:\n",
    "                    ans.pop()\n",
    "                ans.append(x)\n",
    "        return ''.join(ans[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        stack = deque()\n",
    "        letter_count = {}\n",
    "        for letter in s:\n",
    "            if letter not in letter_count:\n",
    "                letter_count[letter] = 1\n",
    "            else:\n",
    "                letter_count[letter] += 1\n",
    "\n",
    "        for letter in s:\n",
    "            if letter not in stack:\n",
    "                while stack and letter < stack[-1] and letter_count[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "                stack.append(letter)\n",
    "            letter_count[letter] -= 1\n",
    "        \n",
    "        return \"\".join(list(stack))\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        stack = []\n",
    "        s_dict = collections.Counter(s)\n",
    "        for c in s:\n",
    "            s_dict[c] -= 1\n",
    "            if c not in stack:\n",
    "                while stack and stack[-1] > c and s_dict[stack[-1]] > 0: \n",
    "                    stack.pop()\n",
    "                stack.append(c)\n",
    "        return ''.join(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        #字典序最小 单调栈 返回单调栈\n",
    "        #包含所有不同字符\n",
    "        stack = []\n",
    "        cnt = {}\n",
    "        visited = set()\n",
    "        for ch in s:\n",
    "            cnt[ch] = cnt.get(ch, 0) +1\n",
    "        for i in range(len(s)):\n",
    "            #需要记录每个字符是否出现在栈中。\n",
    "            if s[i] in visited:\n",
    "                cnt[s[i]] -= 1 #\n",
    "                continue \n",
    "            while stack and s[i]<stack[-1]:#等于不用pop \n",
    "                if cnt.get(stack[-1],0)  <= 0:#后面没有了就不需要pop了\n",
    "                    break  \n",
    "                visited.remove(stack[-1])\n",
    "                stack.pop() \n",
    "                \n",
    "            stack.append(s[i])\n",
    "            cnt[s[i]] -= 1\n",
    "            visited.add(s[i])\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        cnt = [0]*255\n",
    "        for i in s:\n",
    "            cnt[ord(i)] += 1\n",
    "        i = 0\n",
    "        n = len(s)\n",
    "        stk = []\n",
    "        while i < n:\n",
    "            if stk == []:\n",
    "                stk.append(s[i])\n",
    "            else:\n",
    "                if stk[-1] < s[i]:\n",
    "                    if s[i] not in stk:\n",
    "                        stk.append(s[i])\n",
    "                elif stk[-1] == s[i]:\n",
    "                    None\n",
    "                else:\n",
    "                    if s[i] not in stk:\n",
    "                        t = len(stk)\n",
    "                        j = t-1\n",
    "                        while j >= 0 and stk[-1] > s[i]:\n",
    "                            if cnt[ord(stk[j])] != 0:\n",
    "                                stk.pop(j)\n",
    "                            else:\n",
    "                                break\n",
    "                            j -= 1\n",
    "                        stk.append(s[i])\n",
    "            cnt[ord(s[i])] -= 1\n",
    "            i += 1\n",
    "        return ''.join(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        last_index = [0] * 26\n",
    "        for i, ch in enumerate(s):\n",
    "            last_index[ord(ch) - ord('a')] = i\n",
    "        stack = []\n",
    "        visited = [False] * 26\n",
    "        for i, ch in enumerate(s):\n",
    "            if visited[ord(ch) - ord('a')]:\n",
    "                continue\n",
    "            while stack and stack[-1] > ch and last_index[ord(stack[-1]) - ord('a')] > i:\n",
    "                top = stack.pop()\n",
    "                visited[ord(top) - ord('a')] = False\n",
    "            stack.append(ch)\n",
    "            visited[ord(ch) - ord('a')] = True\n",
    "        return ''.join(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        ans = []\n",
    "        visited = [False] * 26\n",
    "        nums = [0] * 26\n",
    "        for char in s:\n",
    "            nums[ord(char) - ord('a')] += 1\n",
    "\n",
    "        for char in s:\n",
    "            if not visited[ord(char) - ord('a')]:\n",
    "                while ans and ans[-1] > char and nums[ord(ans[-1]) - ord('a')]:\n",
    "                    x = ans.pop()\n",
    "                    visited[ord(x) - ord('a')] = False\n",
    "                visited[ord(char) - ord('a')] = True\n",
    "                ans.append(char)\n",
    "            nums[ord(char) - ord('a')] -= 1\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        stack = []\n",
    "        letter_counts = dict()\n",
    "        for ch in s:\n",
    "            letter_counts[ch] = letter_counts.get(ch, 0) + 1\n",
    "        for ch in s:\n",
    "            if ch not in stack:\n",
    "                while stack and ch < stack[-1] and letter_counts[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "                stack.append(ch)\n",
    "            letter_counts[ch] -= 1\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        stack = []\n",
    "        visited = [0] * 256\n",
    "        for ele in s:\n",
    "            cnt[ele] -= 1\n",
    "            if visited[ord(ele)]:\n",
    "                continue\n",
    "            while stack and stack[-1] > ele and cnt[stack[-1]]:\n",
    "                cur = stack.pop()\n",
    "                visited[ord(cur)] = 0\n",
    "            stack.append(ele)\n",
    "            visited[ord(ele)] = 1\n",
    "        return  \"\".join(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        q = []\n",
    "        remain = collections.Counter(s)\n",
    "        for c in s:\n",
    "            if c not in q:\n",
    "                while q and q[-1] > c and remain[q[-1]] > 0:\n",
    "                    q.pop()\n",
    "                q.append(c)\n",
    "            remain[c] -= 1\n",
    "        return ''.join(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        #字典序最小 单调栈 返回单调栈\n",
    "        #包含所有不同字符\n",
    "        stack = []\n",
    "        cnt = {}\n",
    "        visited = set()\n",
    "        for ch in s:\n",
    "            cnt[ch] = cnt.get(ch, 0) +1\n",
    "        for i in range(len(s)):\n",
    "            #需要记录每个字符是否出现在栈中。\n",
    "            if s[i] not in visited: \n",
    "                while stack and s[i]<stack[-1]:#等于不用pop \n",
    "                    if cnt.get(stack[-1],0)  <= 0:#后面没有了就不需要pop了\n",
    "                        break  \n",
    "                    visited.remove(stack[-1])\n",
    "                    stack.pop() \n",
    "                    \n",
    "                stack.append(s[i])\n",
    "                visited.add(s[i])\n",
    "            cnt[s[i]] -= 1\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        ans = [0] * 26\n",
    "        for i in s:\n",
    "            ans[ord(i) - ord('a')] += 1\n",
    "        res = []\n",
    "        in_res = set()\n",
    "        for c in s:\n",
    "            ans[ord(c) - ord('a')] -= 1\n",
    "            if c in in_res:  # ans 中不能有重复字母\n",
    "                continue\n",
    "            while res and c < res[-1] and ans[ord(res[-1]) - ord('a')] > 0:\n",
    "                in_res.remove(res.pop())\n",
    "            res.append(c)\n",
    "            in_res.add(c)\n",
    "        return ''.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        stack = deque()\n",
    "        lowercase_chars = string.ascii_lowercase  # 获取小写英文字符集合\n",
    "        letter_count = {char: 0 for char in lowercase_chars}\n",
    "        for letter in s:\n",
    "            letter_count[letter] += 1\n",
    "\n",
    "        for letter in s:\n",
    "            if letter not in stack:\n",
    "                while stack and letter < stack[-1] and letter_count[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "                stack.append(letter)\n",
    "            letter_count[letter] -= 1\n",
    "        \n",
    "        return \"\".join(list(stack))\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        remain_counter=collections.Counter(s)\n",
    "        stack=[]\n",
    "        for cha in s:\n",
    "            if cha not in stack:\n",
    "                while stack and cha<stack[-1] and remain_counter[stack[-1]]>0:\n",
    "                    stack.pop()\n",
    "                stack.append(cha)\n",
    "            remain_counter[cha]-=1\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        stack=[]\n",
    "        count={}\n",
    "        for ch in s:\n",
    "            if ch not in count:\n",
    "                count[ch]=1\n",
    "            else:\n",
    "                count[ch]+=1\n",
    "        for ch in s:\n",
    "            if ch not in stack:\n",
    "                while stack and ch<stack[-1] and count[stack[-1]]>0:\n",
    "                    stack.pop()\n",
    "                stack.append(ch)\n",
    "            count[ch]-=1\n",
    "        \n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        \"\"\"\n",
    "        单调栈\n",
    "        具体算法:\n",
    "        建立一个字典。其中key为字符c, value为其出现的剩余次数。\n",
    "        从左往右遍历字符串，每次遍历到一个字符，其剩余出现次数– 1.\n",
    "        对于每一个字符，如果其对应的剩余出现次数大于0，我们可以选择丢弃(也可以选择不丢弃)，否则不可以丢弃。\n",
    "        是否丢弃的标准：如果栈中相邻的元素字典序更大，那么我们选择丢弃相邻的栈中的元素。\n",
    "        栈内剩余的就是需要保留的字符\n",
    "        \"\"\"\n",
    "        seen = set() #记录是否在栈内\n",
    "        stack = []\n",
    "        counter = Counter(s)\n",
    "        for c in s:\n",
    "            if c not in seen:\n",
    "                while stack and c<stack[-1] and counter[stack[-1]]>0:\n",
    "                    seen.remove(stack.pop())\n",
    "                stack.append(c)\n",
    "                seen.add(c)\n",
    "            counter[c] -= 1\n",
    "        return \"\".join(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        left = Counter(s)  # 统计每个字母的出现次数\n",
    "        ans = []\n",
    "        in_ans = set()\n",
    "        for c in s:\n",
    "            left[c] -= 1\n",
    "            if c in in_ans:  # ans 中不能有重复字母\n",
    "                continue\n",
    "            # (设 x=ans[-1]) 如果 c < x，且右边还有 x，那么可以把 x 去掉，\n",
    "            # 因为后面可以重新把 x 加到 ans 中\n",
    "            while ans and c < ans[-1] and left[ans[-1]]:\n",
    "                in_ans.remove(ans.pop())  # 标记 x 不在 ans 中\n",
    "            ans.append(c)  # 把 c 加到 ans 的末尾\n",
    "            in_ans.add(c)  # 标记 c 在 ans 中\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        tmp_set = set(s)\n",
    "        limit_dic = Counter(s)\n",
    "        # ({'a': 1, 'c': 1, 'd': 1, 'b': 1})\n",
    "        stack = []\n",
    "        for i in s:\n",
    "            if i not in stack:\n",
    "                while stack and limit_dic[stack[-1]] and ord(i) < ord(stack[-1]):\n",
    "                    stack.pop()\n",
    "                stack.append(i)\n",
    "            limit_dic[i] -= 1\n",
    "        res = ''\n",
    "        for i in stack[:len(tmp_set)]:\n",
    "            res += i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "        res = []\n",
    "        for chs in s:\n",
    "            if chs not in res:\n",
    "                while res and chs < res[-1] and c[res[-1]] > 0:\n",
    "                    res.pop()\n",
    "                res.append(chs)\n",
    "            c[chs] -= 1\n",
    "        return ''.join(res)\n",
    "           \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        ans = []\n",
    "        in_ans = set()\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            if c in in_ans:\n",
    "                continue\n",
    "            while ans and c < ans[-1] and cnt[ans[-1]]:\n",
    "                in_ans.remove(ans.pop())\n",
    "            ans.append(c)\n",
    "            in_ans.add(c)\n",
    "        return ''.join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        stk = []\n",
    "\n",
    "        counter = [0] * 256\n",
    "        for c in s:\n",
    "            counter[ord(c)] += 1\n",
    "\n",
    "        inStack = [False] * 256\n",
    "\n",
    "        for c in s:\n",
    "            counter[ord(c)] -= 1\n",
    "\n",
    "            if inStack[ord(c)]:\n",
    "                continue\n",
    "\n",
    "            while stk and stk[-1] > c:\n",
    "                if counter[ord(stk[-1])] == 0:\n",
    "                    break\n",
    "                inStack[ord(stk.pop())] = False\n",
    "\n",
    "            stk.append(c)\n",
    "            inStack[ord(c)] = True\n",
    "\n",
    "        return \"\".join(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        \n",
    "        con = dict()\n",
    "\n",
    "        for i in s:\n",
    "            if i not in con:\n",
    "                con[i] = 1\n",
    "            else:\n",
    "                con[i] += 1\n",
    "\n",
    "        stack = []\n",
    "        dic = set()\n",
    "\n",
    "        for i in s:\n",
    "            if i not in dic:\n",
    "                while stack and i < stack[-1] and con[stack[-1]] > 0:\n",
    "                    dic.discard(stack.pop())\n",
    "                dic.add(i)\n",
    "                stack.append(i)\n",
    "            con[i] -= 1\n",
    "\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        tmp_dict = defaultdict(int)\n",
    "        for value in s:\n",
    "            tmp_dict[value] += 1\n",
    "        m = len(tmp_dict.keys())\n",
    "        stack = []\n",
    "        for value in s:\n",
    "            if value not in stack:\n",
    "                while stack and stack[-1] > value and tmp_dict[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "                stack.append(value)\n",
    "            tmp_dict[value] -= 1\n",
    "\n",
    "        return \"\".join(stack[:m])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        \n",
    "        stack = [' ']\n",
    "        char_set = set()\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            if c in char_set:\n",
    "                continue\n",
    "            while c <= stack[-1] and cnt[stack[-1]]:\n",
    "                char_set.remove(stack.pop())\n",
    "            stack.append(c)\n",
    "            char_set.add(c)\n",
    "        return ''.join(stack[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 单调栈\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        # 存放去重的结果\n",
    "        stk = deque()\n",
    "        # 布尔数组初始值为false，记录栈中是否存在某个字符 # 输入字符均为ASCII字符，所以大小256够用了 \n",
    "        inStack = {}\n",
    "        count = defaultdict(int)\n",
    "        for i in s:\n",
    "            count[i] += 1\n",
    "        for c in s:\n",
    "        # 每遍历过一个字符 都将对应的计数减一 \n",
    "            count[c] -= 1\n",
    "            # 如果字符c存在栈中 直接跳过 \n",
    "            if inStack.get(c,False):\n",
    "                continue\n",
    "            else:\n",
    "            # 插入之前 和之前的元素比较一下大小\n",
    "            # 如果字典序比前面的小 pop前面的元素 \n",
    "                while len(stk) > 0 and stk[-1] > c:\n",
    "                    # 若之后不存在栈顶元素了 则停止pop \n",
    "                    if count[stk[-1]] == 0:\n",
    "                        break\n",
    "                    # 若之后还有 则可以pop\n",
    "                    # 弹出栈顶元素 并把该元素标记为不在栈中 \n",
    "                    inStack[stk.pop()] = False\n",
    "                stk.append(c)\n",
    "                inStack[c] = True\n",
    "        ret = \"\"\n",
    "        while len(stk) > 0:\n",
    "            ret += stk.pop()\n",
    "        # 栈中元素插入顺序是反的 需要reverse一下 \n",
    "        return ret[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        left = Counter(s)  # 统计每个字母的出现次数\n",
    "        ans = []\n",
    "        in_ans = set()\n",
    "        for c in s:\n",
    "            left[c] -= 1\n",
    "            if c in in_ans:  # ans 中不能有重复字母\n",
    "                continue\n",
    "            # (设 x=ans[-1]) 如果 c < x，且右边还有 x，那么可以把 x 去掉，\n",
    "            # 因为后面可以重新把 x 加到 ans 中\n",
    "            while ans and c < ans[-1] and left[ans[-1]]:\n",
    "                in_ans.remove(ans.pop())  # 标记 x 不在 ans 中\n",
    "            ans.append(c)  # 把 c 加到 ans 的末尾\n",
    "            in_ans.add(c)  # 标记 c 在 ans 中\n",
    "        return ''.join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        c = [0]*26\n",
    "        for i in s:\n",
    "            c[ord(i)-ord('a')] += 1\n",
    "        node = {}\n",
    "        for i in range(26):\n",
    "            if c[i]>0:\n",
    "                node[chr(ord('a')+i)]= False\n",
    "        stack = []\n",
    "        start = 0\n",
    "        for i in range(len(s)):\n",
    "            while stack and stack[-1]>s[i] and c[ord(stack[-1])-ord('a')] >0 and node[s[i]]==False:\n",
    "                top = stack.pop()\n",
    "                node[top] = False\n",
    "            if node[s[i]]== False:\n",
    "                stack.append(s[i])\n",
    "                node[s[i]] = True\n",
    "            c[ord(s[i])-ord('a')]-=1\n",
    "  \n",
    "        return \"\".join(stack)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        cnt_remain = Counter(s)\n",
    "        stack = []\n",
    "\n",
    "        for c in s:\n",
    "            cnt_remain[c] -= 1\n",
    "            if not stack:\n",
    "                stack.append(c)\n",
    "                continue\n",
    "            \n",
    "            if c in stack:\n",
    "                continue\n",
    "            \n",
    "            while stack:\n",
    "                head = stack[-1]  # peek\n",
    "                if not cnt_remain[head]:\n",
    "                    break\n",
    "                if head > c:\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            stack.append(c)\n",
    "\n",
    "        return \"\".join(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        ctr = Counter(s)\n",
    "        N = len(s)\n",
    "        stack = []\n",
    "        checkset = set()\n",
    "        for c in s:\n",
    "            if c in checkset:\n",
    "                ctr[c]-=1\n",
    "                continue \n",
    "            while len(stack)>0 and stack[-1]>=c and ctr[stack[-1]]>0:\n",
    "                pc = stack.pop()\n",
    "                # print(pc,checkset)\n",
    "                checkset.remove(pc)\n",
    "            stack.append(c)\n",
    "            checkset.add(c)\n",
    "            ctr[c]-=1\n",
    "        return \"\".join(stack)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        lastIndex = [0] * 256\n",
    "        for i, c in enumerate(s):\n",
    "            lastIndex[ord(c)] = i \n",
    "        for i in range(n):\n",
    "            c = s[i]\n",
    "            if c in stack:\n",
    "                continue\n",
    "            while stack and stack[-1] > c and lastIndex[ord(stack[-1])] > i:\n",
    "                stack.pop()\n",
    "            stack.append(s[i])\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        stack = deque()\n",
    "        lowercase_chars = string.ascii_lowercase  # 获取小写英文字符集合\n",
    "        letter_count = {char: 0 for char in lowercase_chars}\n",
    "        for letter in s:\n",
    "            letter_count[letter] += 1\n",
    "\n",
    "        for letter in s:\n",
    "            if letter not in stack:\n",
    "                while stack and letter < stack[-1] and letter_count[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "                stack.append(letter)\n",
    "            letter_count[letter] -= 1\n",
    "        \n",
    "        return \"\".join(list(stack))\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        stack = list()\n",
    "        seen = set()\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            if c in seen: \n",
    "                continue\n",
    "            while stack and stack[-1] > c and cnt[stack[-1]] != 0:\n",
    "                seen.remove(stack.pop()) \n",
    "            stack.append(c)\n",
    "            seen.add(c)\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, S: str) -> str:\n",
    "        last = {c: i for i, c in enumerate(S)}\n",
    "        stack = []\n",
    "        for i, c in enumerate(S):\n",
    "            if c in stack: continue\n",
    "            while stack and stack[-1] > c and i < last[stack[-1]]:\n",
    "                stack.pop()\n",
    "            stack.append(c)\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        stack = []\n",
    "        seen = set()\n",
    "        remain_counter = collections.Counter(s)\n",
    "\n",
    "        for c in s:\n",
    "            if c not in seen:\n",
    "                while stack and c < stack[-1] and  remain_counter[stack[-1]] > 0:\n",
    "                    seen.discard(stack.pop())\n",
    "                seen.add(c)\n",
    "                stack.append(c)\n",
    "            remain_counter[c] -= 1\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        stack = deque()\n",
    "        letter_count = {}\n",
    "        for letter in s:\n",
    "            if letter not in letter_count:\n",
    "                letter_count[letter] = 1\n",
    "            else:\n",
    "                letter_count[letter] += 1\n",
    "\n",
    "        for letter in s:\n",
    "            if letter not in stack:\n",
    "                while stack and letter < stack[-1] and letter_count[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "                stack.append(letter)\n",
    "            letter_count[letter] -= 1\n",
    "        \n",
    "        return \"\".join(list(stack))\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        stack,c = collections.deque(),collections.Counter(s)\n",
    "        for e in s:\n",
    "            if e not in stack:\n",
    "                while stack and stack[-1]>e and c[stack[-1]]>0:\n",
    "                    stack.pop()\n",
    "                stack.append(e)\n",
    "            c[e]-=1\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        dic = defaultdict(int) #统计次数\n",
    "        visit = defaultdict(int) #统计stack是否已经存在\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            dic[c] -= 1\n",
    "            if visit[c] == 1:#如果它已经存在于栈中，则不能加入字符\n",
    "                continue\n",
    "            while stack and ord(c)<ord(stack[-1]) and dic[stack[-1]]>0:#在弹出栈顶字符时，如果字符串在后面的位置上再也没有这一字符，则不能弹出栈顶字符\n",
    "                tmp = stack.pop()\n",
    "                # dic[tmp] -= 1\n",
    "                visit[tmp] = 0\n",
    "            stack.append(c)\n",
    "            visit[c] = 1\n",
    "\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        import collections\n",
    "        count = collections.defaultdict(int)\n",
    "        for ch in s:\n",
    "            count[ch] += 1\n",
    "        instack = [False]*256\n",
    "        stk = []\n",
    "        for ch in s:\n",
    "            count[ch] -= 1\n",
    "            if instack[ord(ch)]:\n",
    "                continue\n",
    "            while stk and count[stk[-1]] > 0 and stk[-1] > ch :\n",
    "                instack[ord(stk.pop())] = False\n",
    "            instack[ord(ch)] = True\n",
    "            stk.append(ch)\n",
    "        return ''.join(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        stack = deque()\n",
    "        lowercase_chars = string.ascii_lowercase  # 获取小写英文字符集合\n",
    "        letter_count = {char: 0 for char in lowercase_chars}\n",
    "        for letter in s:\n",
    "            letter_count[letter] += 1\n",
    "\n",
    "        for letter in s:\n",
    "            if letter not in stack:\n",
    "                while stack and letter < stack[-1] and letter_count[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "                stack.append(letter)\n",
    "            letter_count[letter] -= 1\n",
    "        \n",
    "        return \"\".join(list(stack))\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        ans = []\n",
    "        vis = set()\n",
    "        for i, c in enumerate(s):\n",
    "            cnt[c] -= 1\n",
    "            if c in vis: continue\n",
    "            while ans and ans[-1] > c and cnt[ans[-1]]:\n",
    "                vis.remove(ans[-1])\n",
    "                ans.pop()\n",
    "            ans.append(c)\n",
    "            vis.add(c)\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        stack = deque()\n",
    "        letter_count = {char: 0 for char in string.ascii_lowercase}\n",
    "        for letter in s:\n",
    "            letter_count[letter] += 1\n",
    "\n",
    "        for letter in s:\n",
    "            if letter not in stack:\n",
    "                while stack and letter < stack[-1] and letter_count[stack[-1]] > 0:\n",
    "                    stack.pop()\n",
    "                stack.append(letter)\n",
    "            letter_count[letter] -= 1\n",
    "        \n",
    "        return \"\".join(list(stack))\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        # 字典序最小\n",
    "        left = Counter(s)\n",
    "        ans = []\n",
    "        in_ans = set()\n",
    "        for c in s:\n",
    "            left[c] -= 1\n",
    "            if c in in_ans:\n",
    "                continue\n",
    "            \n",
    "            while ans and c < ans[-1] and left[ans[-1]]:\n",
    "                in_ans.remove(ans.pop())\n",
    "            ans.append(c)\n",
    "            in_ans.add(c)\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str) -> str:\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        used = set()\n",
    "\n",
    "        for c in s:\n",
    "            if c not in used:\n",
    "                while ans and ans[-1] > c and cnt[ans[-1]]:\n",
    "                    used.remove(ans.pop())\n",
    "                used.add(c)\n",
    "                ans.append(c)\n",
    "            cnt[c] -= 1\n",
    "        return ''.join(ans)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
